#ifndef AVLTREE_H_INCLUDED
#define AVLTREE_H_INCLUDED
#include <iostream>
#include <algorithm>
#include <unistd.h>
using namespace std;


class AvlTree{
    struct Node{
        Node * left;
        Node * right;
        int height;
        int value;

        Node(int x, Node * l, Node *r):value(x),left(l),right(r),height(0){
        }
    };


public:
    AvlTree():root(NULL){

    }
    ~AvlTree(){
        makeEmpty(root);
    }

    void insert_node(int x)
    {
        insert_node(x,root);
    }

    void printTree()
    {
        printnodes(root);
    }

private:
    int height(Node * t)
    {
        return t == NULL ? -1:t->height;
    }
    void rotateWithLeftChild(Node *&t)
    {
        cout << "rotate " << t->value << " with left child" << endl;
        Node * k2 = t->left;
        t->left = k2->right;
        k2->right = t;
        t = k2;

    }

    void rotateWithRightChild(Node *&t)
    {
        cout << "rotate " << t->value << " with right child" << endl;
        Node * k2 = t->right;
        t->right = k2->left;
        k2->left = t;
        t = k2;
    }



    void doubleRotateAtLeft(Node *&t);

    Node * root;

    void insert_node(int x, Node *&t)
    {
        if(t == NULL)
            t = new Node(x,NULL,NULL);

        else if(x < t->value)
        {
            insert_node(x,t->left);

            if(height(t->left) - height(t->right) == 2)
            {
                cout << "balance broken" <<endl;
                if(x < t->left->value)
                {
                    /*left-left*/
                    rotateWithLeftChild(t);
                }
                else{
                    cout << "double rotate at left" << endl;
                    rotateWithRightChild(t->left);
                    rotateWithLeftChild(t);

                }

            }


        }
        else if(x > t->value)
        {
            insert_node(x, t->right);

            if(height(t->left) - height(t->right) == -2)
            {
                cout << "balance broken" <<endl;
                if(x > t->right->value)
                {
                    /*left-left*/
                    rotateWithRightChild(t);
                }
                else{
                    cout << "double rotate at right" << endl;
                    rotateWithLeftChild(t->right);
                    rotateWithRightChild(t);

                }

            }

        }
        else if(x == t->value)
        {

        }
         t->height = max(height(t->left), height(t->right)) + 1;

    }


    void makeEmpty(Node *&t)
    {
        if(t == NULL)
            return;
        if(t->left != NULL)
            makeEmpty(t->left);
        if(t->right != NULL)
            makeEmpty(t->right);
        if(t->left == NULL & t->right == NULL)
        {
            delete t;
            t = NULL;
        }

    }

    void printnodes(Node *t)
    {
        if(t == NULL)
            return;
        printnodes(t->left);
        cout << t->value << endl;
        printnodes(t->right);

    }



};


#endif // AVLTREE_H_INCLUDED
